package com.zhanghp.class006;

/**
 * 峰值元素是指其值严格大于左右相邻值的元素
 * 给你一个整数数组 nums，已知任何两个相邻的值都不相等
 * 找到峰值元素并返回其索引
 * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 * 你可以假设 nums[-1] = nums[n] = 无穷小
 * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
 *
 * @author zhanghp
 * @since 2024/3/5 11:39
 */
public class Code04_FindPeakElement {
    // 测试链接 : https://leetcode.cn/problems/find-peak-element/
    static class Solution {
        public static int findPeakElement(int[] arr) {
            if (arr == null || arr.length == 0) {
                return -1;
            }
            int n = arr.length;
            if (n == 1 || arr[0] > arr[1]) {
                return 0;
            }
            if (arr[n - 1] > arr[n - 2]) {
                return n - 1;
            }
            // 1 和 n-2都不是
            // (mid-1) 和 (mid + 1)越界，所以也很好解决这个问题
            int l = 1, r = n - 2, mid = 0, ans = -1;
            while (l <= r) {
                mid = l + ((r - l) >> 1);
                if (arr[mid] < arr[mid - 1]) {
                    r = mid - 1;
                } else if (arr[mid] < arr[mid + 1]) {
                    l = mid + 1;
                } else {
                    ans = mid;
                    break;
                }
            }
            return ans;
        }
    }
}
